// https://www.lintcode.com/problem/longest-increasing-subsequence/my-submissions


// O(n2) 解法：

// Dp[i] 表示以第i个数字为结尾的最长上升子序列的长度。
// 对于每个数字，枚举前面所有小于自己的数字 j，Dp[i] = max{Dp[j]} + 1. 如果没有比自己小的，Dp[i] = 1;

// O(nlogn)解法：

// 使用一个辅助空间B数组。
// B[i]存储Dp值为i的最小的数字。（有多个位置，以这些位置为结尾的LIS长度都为i， 则这些数字中最小的一个存在B[i]中）
// 则B数组严格递增。且下标表示LIS长度，也是严格递增，可以在B数组中进行二分查找。

// 对于每个位置i，我们要找，所有小于A[i], 且Dp值最大的那个。这个操作在B数组中二分查找。


class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> &nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> res(n, 1);
        int maxRes = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                {
                    res[i] = max(res[i], res[j] + 1); 
                }
            }
            maxRes = max(maxRes, res[i]);
        }
        // return res.back(); 注意不是最后的答案
        // int maxRes = 1; 可以放到过程中去
        // for (int i = 0; i < n; ++i)
        // {
        //     if (res[i] > maxRes)
        //         maxRes = res[i];
        // }
        return maxRes;
    }
};